lpunbfandomcom-20200214-history
2019.1 Grupo 1: Jogo dos N em Golang
Integrantes Leonardo Rodrigues de Souza - 17/0060543 Lucas Vinicius Magalhães Pinheiro - 17/0061001 Luthiery Costa Cavalcante - 17/0040631 Pedro Vitor Valença Mizuno - 17/0043665 Rafael Gonçalves de Paulo - 17/0043959 Linguagem Go Origem Go é uma linguagem criada pela Google e lançada em código livre em 2009, de paradigma majoritariamente imperativo, que ainda assim simula diversas funcionalidades de linguagens orientadas a objetos. Ela foi pensada com uma sintaxe similar a linguagem C, e sua principal característica que o diferencia de C é o uso nativo de multithreading ''e o uso do ''garbage collector para limpeza de memória''.'' Durante o final da primeira década do século 21, uma das preocupações no meio de hardware era o início de falha da lei de Moore, onde teoricamente a capacidade de processamento aumentaria junto com o número de transistores. Entretanto, por volta de 2005, a capacidade de processamento single-thread começou a estagnar, mesmo com o aumento do número de transistores. Foi nessa época que se intensificou a pesquisa para desenvolvimento de processadores multicore e também o uso de multithreading. É nessa base que Go foi pensada. Características * Além de multithreading, como comentado acima, outras características de Go são tipagem estática, inferência de tipos, e coletor de lixo. * Go também possui um recurso chamado canal, um recurso de sincronização entre várias'' GoRoutine''. * Não há palavras reservadas. * Go possui desvios incondicionais. * Não é necessário o uso do ponto-e-vírgula. Motivação Portanto, Go que é uma linguagem C-Like, foi desenvolvida para eliminar a complexidade de linguagens como C++, Java e etc. Lançado em Março de 2012 Go 1.0 já possui-a uma ampla documentação, a nível Google, além de bibliotecas e ferramentas próprias e também bem documentadas. Objetivos * Aumento de confiabilidade, e principalmente, tipificação estática. * Eficiência. * Dispensar a necessidade de IDE's. * Suporte a rede e multiprocessamento. * Programação distribuída. * Programação em nuvem. * Paralelismo a nível de hardware. Usuário e Domínio de Programação: O usuário típico de Go consiste em um programador que busca implementar sistemas de software que geralmente utilizam multithreading. Quanto ao domínio de programação, o Go é classificado como uma linguagem de programação de sistema, essa geralmente focada em máquinas multicore. Tipos de variáveis Funções Palavras chaves GO e C Ao compararmos GO com C, é possível destacar alguns pontos principais de diferenças. São eles: Único laço de repetição GO possui apenas um laço de repetição, for, que é usado para as mesmas funcionalidades que for e while em C. E possui ainda mais funcionalidades que em C, e possibilidade de trabalhar com objetos. for j := 0; j <= N; j++ { } //While j := 0 for j <= N; j++ { j = j + 1 } Características de avaliação da linguagem Legibilidade Legibilidade é um aspecto de análise de uma linguagem que diz respeito a quão facilmente um fragmento de código pode ser interpretado por um programador e até mesmo por um leigo em programação, é a relação entre o que um fragmento de código pretende representar e o que ele aparenta representar. É por exemplo, o uso de palavras chaves facilmente reconhecidas, o uso de estruturas simples, a ausência de tags que, embora necessárias para o código, parecem repetitivas ou mesmo desnecessárias para o entendimento humano. Em comparação com C, GO tem legibilidade levemente melhor. Isso se pode checar em coisas simples, como por exemplo, o pedido de impressão de alguma variável no terminal. import "fmt" func main() { a := 88 fmt.Println(a) } Embora Go tenha a função fmt.Printf() que se comporta muito similar à do C, outras funções como acima deixam o código compacto quando não se precisa de uma formatação específica. Escritabilidade Escritabilidade se refere ao quão facilmente a linguagem pode ser usada para fazer programas em determinado domínio. De certo modo, é a liberdade que a linguagem dá ao programador de utilizar suas ferramentas, sem haver compromisso ao funcionamento do código. Alguns parâmetros para a escritabilidade são: * Simplicidade e Ortogonalidade Um número elevado de estruturas disponíveis pela linguagem podem permitir diferentes coisas, mas ao mesmo tempo abrem margem para possíveis mal usos por parte do programador, comprometendo o código. Dessa forma, ter pouca, mas eficiente, estruturas, melhora a escritabilidade de uma linguagem, pois é melhor um conjunto reduzido mas consistente e com regras bem escritas, do que um conjunto amplo e confuso de estruturas e regras. * Suporte para abstração O uso de abstração permite ao programador usar estruturas complexas de forma que é possível omitir certas partes que, para a escrita de um programa, seriam desnecessárias, mas que possivelmente facilitariam o entendimento do código. O grau de abstração permitida por uma linguagem pode aumentar ou diminuir e a facilidade com que essa abstração pode ser representada são dois fatores que impactam na escritabilidade de uma linguagem. A abstração pode ocorrer de dois modos, abstração de processos e abstração de dados. Abstração de processos Denomina o encapsulamento de pedaços de código para que possam ser reusados sem a necessidade de reescrevê-los. Ou seja, o uso de funções e procedures no seu código. Quanto mais amplo for a gama de possibilidades de se usar uma função na linguagem, melhor a escritabilidade. Abstração de dados É a representação encapsulada de dados e métodos vinculados ao respectivo dado, que podem ser acessadas em outras instâncias do código. Ou seja, o uso de orientação a objetos. Expressividade Confiabilidade Quando falamos em confiabilidade de uma linguagem é importante analisar sua consistência, bem como as garantias de que os programas escritos nesta linguagem possuirão a mesma execução sempre. Ou seja, esta linguagem deve se comportar de acordo com sua especificação sob todas as condições e para qualquer execução. Dos principais tópicos de confiabilidade, em GO podemos destacar alguns como: Verificação de tipos: Apesar da linguagem GO oferecer um sistema para tipificação das variáveis automaticamente, ou seja, o compilador consegue inferir o tipo da variável a partir do seu uso. GO possui mecanismos para declaração dos tipos das variáveis. Tal procedimento garante o correto uso de uma variável, que garante o correto funcionamento das subrotinas que a usam. Este é um fator importante em confiabilidade de uma linguagem, uma vez que a verificação de tipos estáticas facilita a correção do problema, bem como adianta a descoberta de erros de tipos em um programa. A verificação de tipos em tempo de execução é deveras custoso e não recomendado. GO é uma linguagem compilada e portanto, sua verificação de tipos é feita em tempo de execução, onde apesar de impactar no tempo de compilação, a verificação de tipos estáticos aumenta substancialmente a confiabilidade nos programas feitos em GO. Entretanto, mesmo com todos os pontos apresentados, GO ainda permite uma inferência de tipo pelo compilador, adicionando uma maior capacidade de escrita na linguagem. Manipulação de exceções: GO não possui uma forma explícita de tratar exceções, sendo este um dos pontos negativos da linguagem. Mas apesar de não possui uma forma concreta, GO implementa em outras funcionalidades diversos sistemas que possibilitam o processo de tratamento de exceções. O principal mecanismo utilizado é o retorno múltiplo de funções, onde cada função retorna seu valor padrão e além disso, retorna também uma flag, ou algum tipo de erro. Graças ao polimorfismo implementado, e a funcionalidade de retorno múltiplo, é possível o correto tratamento de exceções. Entretanto, esta não é uma forma intuitiva, e acaba sendo um tanto complicada. Contudo, ao comparar C e GO, é possível ver que GO possui um aparato de tratamento de erros bem melhor que C, onde o processo é bem menos intuitivo e mais complicado. Aliasing: Legibilidade e capacidade de escrita: Estes que são 2 pontos já analisados também influenciam diretamente na confiabilidade de uma linguagem. Ao analisar GO como um todo é evidente que sua legibilidade é fraca, isso em comparação com outras linguagens modernas. Código escritos em GO necessitam de um tempo de estudo, bem como um conhecimento prévio na linguagem, para que seja completamente entendidos. Além disso, a capacidade de escrita de GO também é afetada pelos mesmos motivos. Entretanto, ao comparar GO com C, os mesmos possuem os mesmos problemas de legibilidade e capacidade de escrita, devido a suas estruturas bem próximas. Contudo, tais pontos negativos são combatidos com sua facilidade e rapidez de escrita de código, com comandos concisos e curtos. Diversos processos de abstração também são implementados em GO, em contrapartida de C, o que facilita ainda mais o desenvolvimento e manutenção de códigos em GO. Em virtude dos pontos mencionados, é possível concluir que GO possui uma confiabilidade superior em relação ao C. C não possui diversos mecanismos para garantir uma boa conduta na execução de uma aplicação, o que GO já possui. Entretanto, se comparar GO com outras linguagens, como JAVA, é possível ver que GO ainda deixa a desejar em alguns aspectos. E portanto, em uma análise geral, GO possui uma confiabilidade Parcial, superior em relação ao C, mas inferior em relação a linguagens já consolidadas e amplamente usadas no mercado. Custo A análise do custo de uma linguagem depende de diversas características. Em especial, depende de todos os pontos já abordados aqui. Em resumo, o custo de uma linguagem é quanto ao treinamento de programadores para desenvolver nela, este que é diretamente impactado pela legibilidade, capacidade de escrita, suporte a abstração e redução de redundâncias. Ao analisar GO, é possível traçar um paralelo de custo bem parecido, se não igual, ao de C. O treinamento de programadores em GO dependem diretamente da aplicação ao qual estes devem desenvolver. GO é uma linguagem muito ampla, e com muitos recursos, e não é necessário seu domínio completo para a escrita de programas. Além disso, GO possui uma estrutura muito semelhante ao C, que já é uma linguagem muito conhecida e consolidada, e portanto diversos programadores, mesmo que nunca tenham programado em GO, possuem conhecimentos suficientemente uteis para desenvolver em GO, uma vez que já tenham programado em C. O segundo ponto principal para análise de custo é quanto a manutenibilidade de aplicações desenvolvidas em GO. E para este ponto é necessário voltar a análise de confiabilidade da linguagem. GO possui uma confiabilidade Parcial, ou seja, ainda possui diversos aspectos fracos, e muitos deles relacionados a erros e seu tratamento. E portanto, o custo de manutenibilidade de aplicações em GO é acrescido por seus pontos fracos. E por fim, para definir o custo de aplicações em GO somente é possível mediante informações da própria aplicação. Isso devido que, apesar dos pontos fracos em algumas categorias aqui expostas, GO ainda é desenvolvida para possuir alta confiabilidade, além de possuir estruturas fixas e consolidadas. O projeto: Jogo dos N O Jogo dos 15 consiste em um tabuleiro 4x4 com 15 blocos numerados de 1 a 15 distribuídos aleatoriamente e um espaço vazio. O objetivo é ordenar deixar os blocos ordenados por meio de movimentos manipulando o espaço vazio, como na figura ao lado. Pode ser generalizado para um tabuleiro de NxN (N>1), onde teremos o Jogo dos N²-1. Nosso exercício é fazer um algoritmo que encontre uma sequência de movimentos para resolver o jogo a partir de qualquer disposição inicial do tabuleiro. Algoritmo A* Representaremos a busca em forma de grafo direcionado, onde cada nó é um estado possível do jogo (onde estão armazenados o estado do tabuleiro, o caminho até chegar nele e a posição do bloco vazio), e onde há aresta entre dois nós A e B se conseguirmos ir de A a B com uma jogada (ação). A busca proposta assemelha-se a uma busca em largura (BFS): # partimos de um nó inicial S; # marque o nó atual como visitado; # se o nó atual é o objetivo, solução encontrada: retorne o caminho achado; # insira todos os vizinhos não-visitados de S numa fila, nesse caso uma fila de prioridade cuja prioridade de cada nó N é sua função heurística f(N); # retire o elemento S2 de menor f, e volte ao passo 2 (nó atual agora é S2). f(n) é a função heurística de um nó n, e aquele que tiver o menor valor f(n) dentre os que estão na fila será o próximo a ser expandido. É definida como f(n) = g(n) + h(n), onde: * g(n) é o custo (qtd. movimentos) de se chegar ao nó n desde o nó inicial * h(n) é uma estimativa de quantos movimentos se precisa para chegar no estado final. * Calcula-se a distância de Manhattan: distância entre a posição atual do bloco i no tabuleiro n e a posição desejada (no tabuleiro final). * Assim, h(n) = somatório das distâncias de Manhattan de todos os blocos no tabuleiro. Usaremos uma busca A* bidirecional: Duas buscas concorrentes executando: uma partindo do início para o fim e outra do fim com objetivo sendo o início. Cada uma tem seu próprio vetor de estados visitados. A cada iteração, uma olha se o nó atual já foi visitado no vetor da outra. Se sim, solução encontrada: o caminho-solução é a junção dos caminhos acumulados nos dois vetores. O resultado da busca é um vetor de direções (movimentos) que o bloco vazio "realizou" desde o nó inicial até o final. Usaremos uma interface gráfica web simples mostrando o processo de resolução do jogo, com as iterações do caminho já achado sobre a matriz do tabuleiro.